package sudoku;

/**
 * The <code>Sudoku</code> class povides a static <code>main</code>
 * method allowing it to be called from the command line to print the
 * solution to a specified Sudoku problem.  
 *
 * <p>The following is an example of a Sudoku problem:
 *
 * <pre>
 * -----------------------
 * |   8   | 4   2 |   6   |
 * |   3 4 |       | 9 1   |
 * | 9 6   |       |   8 4 |
 *  -----------------------
 * |       | 2 1 6 |       |
 * |       |       |       |
 * |       | 3 5 7 |       |
 *  -----------------------
 * | 8 4   |       |   7 5 |
 * |   2 6 |       | 1 3   |
 * |   9   | 7   1 |   4   |
 *  -----------------------
 * </pre>
 * 
 * The goal is to fill in the missing numbers so that
 * every row, column and box contains each of the numbers
 * <code>1-9</code>.  Here is the solution to the
 * problem above:
 *
 * <pre>
 *  -----------------------
 * | 1 8 7 | 4 9 2 | 5 6 3 |
 * | 5 3 4 | 6 7 8 | 9 1 2 |
 * | 9 6 2 | 1 3 5 | 7 8 4 |
 *  -----------------------
 * | 4 5 8 | 2 1 6 | 3 9 7 |
 * | 2 7 3 | 8 4 9 | 6 5 1 |
 * | 6 1 9 | 3 5 7 | 4 2 8 |
 *  -----------------------
 * | 8 4 1 | 9 6 3 | 2 7 5 |
 * | 7 2 6 | 5 8 4 | 1 3 9 |
 * | 3 9 5 | 7 2 1 | 8 4 6 |
 *  -----------------------
 * </pre>
 *
 * Note that the first row <code>187492563</code> contains
 * each number exactly once, as does the first column
 * <code>159426873</code>, the upper-left box
 * <code>187534962</code>, and every other row, column
 * and box.
 *
 * <p>The {@link #main(String[])} method encodes a problem as an array
 * of strings, with one string encoding each constraint in the problem
 * in row-column-value format.  Here is the problem again with
 * the indices indicated:
 *
 * <pre>
 *     0 1 2   3 4 5   6 7 8
 *    -----------------------
 * 0 |   8   | 4   2 |   6   |
 * 1 |   3 4 |       | 9 1   |
 * 2 | 9 6   |       |   8 4 |
 *    -----------------------
 * 3 |       | 2 1 6 |       |
 * 4 |       |       |       |
 * 5 |       | 3 5 7 |       |
 *   -----------------------
 * 6 | 8 4   |       |   7 5 |
 * 7 |   2 6 |       | 1 3   |
 * 8 |   9   | 7   1 |   4   |
 *    -----------------------
 * </pre>
 *
 *The above matrix will be represented as the following string:
 *080402060034000910960000084000216000000000000000357000840000075026000130090701040
 *
 * <p>The full command-line invocation for the above puzzle is:
 * 
 * <pre>
 * % java -cp . Sudoku 080402060034000910960000084000216000000000000000357000840000075026000130090701040
 * </pre>
 * 
 * <p>See <a href="http://en.wikipedia.org/wiki/Sudoku">Wikipedia:
 * Sudoku</a> for more information on Sudoku.
 *
 * <p>The algorithm employed is similar to the standard backtracking
 * <a href="http://en.wikipedia.org/wiki/Eight_queens_puzzle">eight
 * queens algorithm</a>.
 *
 * @version 1.0
 * @author <a href="http://www.colloquial.com/carp">Bob Carpenter</a>
 */
public class SudokuOverView {

    /**
     * Print the specified Sudoku problem and its solution.  The
     * problem is encoded as specified in the class documentation
     * above.
     *
     * @param args The command-line arguments encoding the problem.
     */
	private static final String grid1 ="003020600900305001001806400008102900700000008006708200002609500800203009005010300";
	private static final String grid2 ="043700908005030000010000300600027000407000103000540009002000030000050400504001260";
	private static final String grid3 ="080402060034000910960000084000216000000000000000357000840000075026000130090701040";
	private static final String grid4 ="4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......";
	private static final String grid5 ="52...6.........7.13...........4..8..6......5...........418.........3..2...87.....";
	private static final String grid6 ="6.....8.3.4.7.................5.4.7.3..2.....1.6.......2.....5.....8.6......1....";
	private static final String grid7 ="48.3............71.2.......7.5....6....2..8.............1.76...3.....4......5....";
	private static final String hard1 =".....6....59.....82....8....45........3........6..3.54...325..6..................";
	private static final String hard2 ="000005080000601043000000000010500000000106000300000005530000061000000004000000000";
	public static void main(String[] args) {
    	String grid=grid1.replace('.', '0');
    	char [] grids=grid.toCharArray(); 	
		int[][] matrix = parseProblem(grids);
		writeMatrix(matrix);
		if (solve(0,0,matrix))    // solves in place 
		    writeMatrix(matrix);
		else 
		    System.out.println("NONE");
    }

    static boolean solve(int i, int j, int[][] cells) {
		if (i == 9) {
		    i = 0;
		    if (++j == 9) 
			return true; 
		}
		if (cells[i][j] != 0)  // skip filled cells
		    return solve(i+1,j,cells);
		
		for (int val = 1; val <= 9; ++val) {
		    if (legal(i,j,val,cells)) {  
			cells[i][j] = val;       
			if (solve(i+1,j,cells))  
			    return true;
		    }
		}
		cells[i][j] = 0; // reset on backtrack
		return false;
    }

    static boolean legal(int i, int j, int val, int[][] cells) {
		for (int k = 0; k < 9; ++k)  // row
		    if (val == cells[k][j])
			return false;
	
		for (int k = 0; k < 9; ++k) // col
		    if (val == cells[i][k])
			return false;
	
		int boxRowOffset = (i / 3)*3;
		int boxColOffset = (j / 3)*3;
		for (int k = 0; k < 3; ++k) // box
		    for (int m = 0; m < 3; ++m)
			if (val == cells[boxRowOffset+k][boxColOffset+m])
			    return false;
	
		return true; // no violations, so it's legal
    }

    static int[][] parseProblem(char[] args) {
		int[][] problem = new int[9][9]; // default 0 vals
		int index=0;
		for(int r=0; r<9; r++)
		{
			for(int c=0; c<9; c++)
			{
				problem[r][c]=args[index]-48; //assci 0-9 is 48-57
				index++;
			}
			
		}
		return problem;
    }

    static void writeMatrix(int[][] solution) {
		for (int i = 0; i < 9; ++i) {
		    if (i % 3 == 0)
			System.out.println(" -----------------------");
		    for (int j = 0; j < 9; ++j) {
			if (j % 3 == 0) System.out.print("| ");
			System.out.print(solution[i][j] == 0
					 ? " "
					 : Integer.toString(solution[i][j]));
			
			System.out.print(' ');
		    }
		    System.out.println("|");
		}
		System.out.println(" -----------------------");
	    }

}